<html>
<head><meta http-equiv="Content-Type" content="text/html; charset=GBK">
<title>Lab 2: Lexer and Parser</title>
<link rel="stylesheet" href="../labs.css" type="text/css">
</head>

<body>
<table width="100%">
<tbody>
  <tr>
<td>
<h1>Lab 2: Lexer and Parser</h1>
<hr>

<h3>Lab Overview</h3>
In this lab, you'll
implement the frond-end for <kbd>jcc</kbd>: a
lexer and a parser. The front-end will also generate
abstract syntax trees from Java source.

<h3>Software Setup</h3>
<p>
There are generally two approaches to implement a compiler's
front-end: crafted by hand or used automatically construction
tools. In this lab, you'll experience the second approach.

The lexer is called <code>FsLex</code> and the parser is
called <code>FsYacc</code>. However, these tools are not
distributed by Microsoft's VS, instead, it is offered 
as a 3rd party plugin called
<a href="http://fsharppowerpack.codeplex.com/">powerpack</a> (developed by the same group of folks
at Microsoft). 

<p>
Now, you should download FsLex and FsYacc
<a href="http://fsharppowerpack.codeplex.com/releases/view/40168">here</a>, and
install it on your machine. Important to note, this powerpack
software 
requires .NET framework 3.5, you should download it from
<a href="http://www.microsoft.com/download/en/details.aspx?id=21">here</a> and
install it if you have not.

<p>
Finally, remember to add the binary directory of fsharp powerpack to
your path. And make sure that the command <kbd>fslex, fsyacc</kbd>
works properly on prompt.

<h3>Getting Started</h3>
In each lab, we'll offer you a code skeleton to modify and enhance.
This year, we've decided to put the code repository on Google (for
this courseware is also open-source). Download the code repository here:
...

<p>
If this does not work for you, please let us know.

<h3>Hand-in Procedure</h3>
When you finished your lab, zip you solutions and submit to the
<a href="">school's information system</a>.

<h1>Part A: The Lexer</h1>
The lexer generator for F# is <code>fslex</code> and is re-implemented
by Microsoft F# team following ocamllex. Unfortunately, the documentation for fslex
is poor, with the only official document
<a href="http://fsharppowerpack.codeplex.com/wikipage?title=FsLex%20Documentation&referringTitle=Home">here</a>. 
But as fslex is so close to ocamllex, so the
<a href="http://caml.inria.fr/pub/docs/manual-ocaml/manual026.html">ocamllex documentation</a> may also
be a valueable reference. But keep in mind, there are subtle differences
between fslex and ocamllex, so be careful.



<p>
Now browse the project code we offered you, there are two newly
added files in subdirectory <code>slp</code>: <code>slp/SlpLexer.fsl</code>
and <code>slp/SlpParser.fsy</code>. These two files are the lexer
and parser generator source files for Slp. 

<div class="required">
<p><span class="header">Exercise 1.</span>
In this exercise, you don't need write any code at all, for all
the lexer and parser source code have been finished. Your job is try
to build the lexer and parser on your own, and to understand
what's going on under the hood.

<ul>
<li>
Open a prompt and switch to the directory <code>slp/</code>, type
<pre>
<kbd>  fsyacc --module SlpParser SlpParser.fsy</kbd></pre>
what files are generated? Open these files and try to skim them (don't
try to understand every details, just to get some idea what they are).

<li>
There should exist a datatype look like:
<pre>
  type token = 
  | EOF
  | PRINT
  | ...  // other cases omitted
</pre>
try to locate it in the newly generated files. Where they came from?

<li>
Now, in the same directory, type:
<pre>
<kbd>  fslex --unicode SlpLexer.fsl</kbd></pre>
what new files are generated? Open these files and try to skim them (also
skip details, just to get some idea what they contain).

<li>
Now, try to read the code in <code>main.fs</code>, and try to
understand how to glue the lexer and the parser to build a 
complete front-end for Slp. Make sure you understand every
line of code there.
</ul>

<p>
Note: if you got some exception like this:
<pre>
  Method not found: 'System.Object Microsoft.FSharp.Text.Parsing.Tables`1.Interpret ...
</pre>
go to <a href="http://www.microsoft.com/download/en/details.aspx?id=15834">here</a>, and
reinstall Visual Studio 2010 F# 2.0 Runtime SP1 (choose for repair). This
should be a nasty bug from Microsoft!
</div>

<div class="required">
<p><span class="header">Exercise 2.</span>
Write a lexer for mini-Java as described in the appendix of the
Tiger book. You should start with the provided code skeleton
<code>front-end/Lexer.fsl</code>, and you may refer to the
sample code in the previous exercise. Consult the ocamllex
manual when in doubt.

<p>
Pay special attentions to the following questions during implementing
the lexer:
<ul>
  <li>how to handle positions (file names, line numbers, column numbers, etc.)?
  <li>how to handle nested comments?
</ul>

</div>



<div class="challenge">
<p><span class="header">Challenge!</span>
BST is not very efficient, the worst time for lookup is O(n). Implement
a more efficient variant, such as AVL tree, 2-3-4 tree or red-black
tree. (Hint: the functional style of these data structures are
much simpler and cleaner than the imperative ones, so the
normal textbooks are of less use. Instead, there are some execellent
articles on the web. For
instance, <a href="http://www.cs.cornell.edu/courses/cs3110/2009sp/lectures/lec11.html">here</a>
is a good introduction on red-black trees
using functional style.)
</div>


<h1>Part B: The Parser</h1>
<p>
This part requires you to write a simple program analyzer and 
interpreter for a straight-line programming language <kbd>SLP</kbd>. This 
exercise serves as an introduction to environments (symbol 
tables mapping variable-names to information about the variables);
to abstract syntax (data structures representing the phrase 
structure of programs); to recursion over tree data structures,
useful in many parts of a compiler; and to a functional style of 
programming without assignment statements.

<p>
The definition of SLP language is in grammar 1.3 in chapter 1. You
should read that part carefully and make sure you understand
the meanings of each language struct. Here
is a sample program
</p>
<pre>     
     a = 5+3; 
     b = (print(a, a-1), 10*a); 
     print(b);
</pre>
which will be used throughout this part of the lab. 

<p>When executed, this program print
<pre>
8 7
80
</pre>
on standard out (the screen) when run. That is, each <code>print</code>
will print each of its argument in turn, separated by a space, terminated
by a new line. If there is no aurguments to the <code>print</code>
statement, it merely prints a new line.

<p>
In this lab, you will write two components for this simple programming
language: a simple program analyzer and 
an interpreter.

<p>
Now browse the code we offered. Here is a brief 
discription of these files:

<table valign="top" border="1" >
  <tr>
    <td>slp.fs:</td>
    <td>data structures to define SLP, whose constructors 
      represent abstract syntax tree nodes</td>
  </tr>

  <tr>
    <td>testprog.fs:</td>
    <td>a sample program of SLP, which shows how to construct AST from "slp.fs" given above </td>
  </tr>

  <tr>
    <td>maxarg.fs:</td>
    <td>scan AST of a program, and return the 
      maximum number of arguments of any print statement within 
      any (sub-)expression of the program</td>
  </tr>

  <tr>
    <td>interp.fs:</td>
    <td>scan AST of a program, and interpret the program (i.e., should
    simulate the print behaviour of the scanned program</td>
  </tr>

  <tr>
    <td>main.fs:</td>
    <td>the entry point of whole program</td>
  </tr>
</table>



<h3>Pretty printer</h3>
A pretty printer, as its name suggests, will print some out, but
in a somewhat pretty form. It's a classical problem with decades
of history and numerous interesting applications. Read more about 
pretty printing in computer science 
<a href="http://en.wikipedia.org/wiki/Prettyprint">on the wiki</a>. 
Pretty-print the abstract syntax tree out has the great importance
for debugging: if the printed tree is the same as the desired
source, then we are on the right way.

<div class="required">
<p><span class="header">Exercise 2.</span>
Read the code in file <code>pp.fs</code>. The algorithm for
pretty printing has been (alomost) written for you, make sure you read
and understand the code there. Later in the course, you'll
encouter more fancy pretty printing algorithms, so this one
is a good start point.

<p>
After you read this code, try build the code and run it (in VS2010
, just press
<code>Ctrl+F5</code>), and check how the pretty printing code works.

<p>
Now, it's time for you to write some code. The code printed out
looks like the left one, which is different from the one on
the right as expected. What's the difference? And this difference reveals
that there exists some bug in current code. Try find these bugs
and fix them.
<table>
  <tr>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1,), 10*a); 
        print(b,);
      </pre>
    </td>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
  </tr>
</table>
Dont' forget to test your code when you finished.
</div>

<div class="challenge">
<p><span class="header">Challenge!</span>
There are many more fancy pretty printing algorithms, besides the one
we've offered you. 
<a href="ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/79/770/CS-TR-79-770.pdf">Derek Oppen's paper</a>
is among the first ones to
present a pretty printing routine, based on an imperative style. Later
in 1997, Phillip Wadler presents a
<a href="http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf">functional style
algorithm</a>. 

<p>
Read these papers (or others on your choice), and implement a
pretty printing library based on the
algorithms there. Try your library for printting Slp. Hint: as
you'are using F#, so Wadler's algorithm may be a better candidate.
</div>

<h3>Maximum Number of Arguments</h3>
<p>
There is only one kind of function here in Slp: <code>print</code>, and
<code>print</code> can take a variable number of arguments. For
instance, the first <code>print</code> in previous program
<pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
</pre>
has 2 arguments, whereas the second <code>print</code> only has
1 argument. So the maximum number of arguments in this program is 2.

<div class="required">
<p><span class="header">Exercise 3.</span>
Finish the code in file <code>maxarg.fs</code>. The code you should modify looks like:
<pre>  raise Unimplement
</pre>
So you should find all places marked as this and replace them with your code.
</div>

<h3>Interpreter</h3>
<p>
There is only one kind of function here in Slp: <code>print</code>, and
<code>print</code> can take a variable number of arguments. For
instance, the first <code>print</code> in previous program
<pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
</pre>
has 2 arguments, whereas the second <code>print</code> only has
1 argument. So the maximum number of arguments in this program is 2.

<div class="required">
<p><span class="header">Exercise 4.</span>
Finish the code in file <code>interp.fs</code>. The code you should modify looks like:
<pre>  raise Unimplement
</pre>
So you should find all places marked as this and replace them with your code.
</div>

<h3>Optimization</h3>
<p>
The primary purpose for optimization is to make programs consume
less memory, run faster, etc.. Normally, optimizations are
performed on intermediate representation such as three-address
code or. But as we've discussed the abstract syntax tree
for the language Slp, we can also experiment some simple
optimizations.

<p>
<i>Constant folding</i> is an optimization that calculates
(at compile-time) the result of operations on constants (integer or real
literals, static addresses, etc..). For instance, consider
the previous sample program again on the left, and the result
of constant folding is on the right:
<table>
  <tr>
    <td>
      <pre>
        a = 5+3; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<div class="required">
<p><span class="header">Exercise 5.</span>
Write a function
<pre>  let constFold (s: Slp.stm): Slp.stm = ...
</pre>
which performs constant folding. We have NOT provide
you a skeleton file, so you should create one if necessary. Think the algorithm
carefully before writing your code.
</div>

<p>
<i>Constant propogation</i> is an optimization that substitute
the compile-time constant variable with that constant. For instance, consider
the above sample program again (on the left, which is after constant
folding), and the result
of constant propogation is on the right:
<table>
  <tr>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*a); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        a = 8; 
        b = (print(8, 8-1), 10*8); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<p>
An interesting point is that, as you may observe in the above
example, after this optimization, there may exist chances
for further optimizations (say, constant folding again). So, for
this sample program, there is a cycyle on the two optimizations:
constant folding -> constant propagation -> constant folding ->
constant propogation -> ...

<p>
Is this an infinite loop? That is, how do you know when this
cycyle should stop?

<div class="required">
<p><span class="header">Exercise 6.</span>
Write a function
<pre>  let constProp (s: Slp.stm): Slp.stm = ...
</pre>
which performs constant propogation. Also you should create a new
file if necessary. How should you know whether there is chance to
perform another pass of constant folding? Should you do constant
folding again?
</div>

<p>
<i>Dead code elimination</i> optimization tries to eliminate 
<i>useless</i> code from a given program. For now, we have
not given a formal definition on what is <i>useless</i>, which
will be discusses in a later phase of this course. But, for the
Slp language, the notion of useless is simple: if an assignment
statement assigns value to some variable <i>x</i>, but <i>x</i>
will never be used in futher, then <i>x</i> is useless. For instance, the
variable <code>a</code> in the following left prorgram is
useless, but <code>b</code> is not useless. As a result, one
can eliminate the assignment statement to <code>a</code>, obtaining
the right result:
<table>
  <tr>
    <td>
      <pre>
        a = 8; 
        b = (print(a, a-1), 10*8); 
        print(b);
      </pre>
    </td>
    <td>
      <pre>
        <del>a = 8;</del>
        b = (print(8, 8-1), 10*8); 
        print(b);
      </pre>
    </td>
  </tr>
</table>

<p>
Can the above right program be further optimized? If so, how?

<div class="required">
<p><span class="header">Exercise 7.</span>
Write a function
<pre>  let deadCode (s: Slp.stm): Slp.stm = ...
</pre>
which performs dead code elimination. 

<p>Now, it's a good time to run your interpr again on the final optimized
version of the Slp program. The interpreter should print the same
values for this one as before.
</div>

<div class="challenge">
<p><span class="header">Challenge!</span>
Our version of the compiler optimizes the sample Slp program to
<pre>
  print (8, 7);
  print (80);
</pre>
Can you figure out how this can be done? And try to implement
an algorithm to achieve this. (Hint: you should do code hoisting: to
hoist statements out of expressions.)
</div>



<h1>Part C: Abstract Syntax Tree for Java</h1>
This part presents the abstract syntax trees for mini-Java (abbr. Java), 
<h3>Handin</h3>
This completes the lab. Remember to hand in your solution to 
the information system. How long does it take you to finish this lab?

</td>
</tr>
  
</tbody>
</table>


</body>
</html>
